package com.lga.algorithm;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * leetCode 3. 无重复字符的最长子串
 *
 * @author lga
 */
public class LengthOfLongestSubstring {

    public static int lengthOfLongestSubstring(String s) {
        //不含有重复字符的 最长子串 的长度。
        int maxLengthOfSubstring = 0;

        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <=s.length(); j++) {
                if (isUnique(s, i, j)) {
                    maxLengthOfSubstring =  Math.max(maxLengthOfSubstring, j - i);
                }
            }
        }
        return maxLengthOfSubstring;
    }

    /**
     * 用于判断子串中是否有重复的字符
     * @param s
     * @param start
     * @param end
     * @return
     */
    public static boolean isUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) {
                return false;
            }
            set.add(ch);
        }
        return true;

    }

    /**
     * 滑动窗口算法
     * @param s
     * @return
     */
    public static int  fun1(String s) {
        int max = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        int left = 0;
        for (int i = 0; i < s.length(); i++) {
            //发生重复的情况
            if (map.containsKey(s.charAt(i))) {
                //left重新复制为重复值的后一个下标值
                left = Math.max(left, map.get(s.charAt(i))+1);
            }
            map.put(s.charAt(i), i);
            max = Math.max(max,i-left+1);
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(fun1("pwwkew"));
    }
}
